/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: BitmapTraverserTask.java
 * Written by: Daniel Schmidt
 * 
 * This code has been developed at the Karlsruhe Institute of Technology (KIT), Germany, 
 * as part of the course "Multicore Programming in Practice: Tools, Models, and Languages".
 * Contact instructor: Dr. Victor Pankratius (pankratius@ipd.uka.de)
 *
 * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.plugins.minarea.mk01.bitmapTraverser;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.RecursiveTask;

import com.sun.electric.api.minarea.ErrorLogger;
import com.sun.electric.api.minarea.geometry.Point;
import com.sun.electric.plugins.minarea.mk01.datatypes.MinAreaPolygon;
import com.sun.electric.plugins.minarea.mk01.datatypes.Pair;
import com.sun.electric.plugins.minarea.mk01.datatypes.Side;

@SuppressWarnings("serial")
public class BitmapTraverserTask extends RecursiveTask<List<MinAreaPolygon>> {

	protected static int THRESHOLD;
	private BitSet[] bitMap;
	private int[] indexToXCoordinate;
	private int[] indexToYCoordinate;
	private int start;
	private int end;
	private ErrorLogger errorLogger;
	private long minArea;
	
	/**
	 * C'tor
	 * 
	 * @param bitMap
	 * @param indexToXCoordinate
	 * @param indexToYCoordinate
	 * @param start
	 * @param end
	 * @param errorLogger
	 * @param minArea
	 */
	public BitmapTraverserTask(BitSet[] bitMap, int[] indexToXCoordinate, int[] indexToYCoordinate,
			int start, int end, ErrorLogger errorLogger, long minArea) {

		this.bitMap = bitMap;
		this.indexToXCoordinate = indexToXCoordinate;
		this.indexToYCoordinate = indexToYCoordinate;
		this.start = start;
		this.end = end;
		this.errorLogger = errorLogger;
		this.minArea = minArea;
	}
	
	/**
	 * The Phase 3 of the MinAreaChecking-Algorithm at first splits up the whole bitmap
	 * in different vertical stripes of equal size. For each stripe a separate task is executed 
	 * in parallel. If the resulting range is less than the specified THRESHOLD, the polygons within 
	 * the single stripes can be build up. After that those polygons that are connected with each
	 * other across the borders get merged till they are completely enclosed and finally checked 
	 * against the fulfilling of the minimum area constraint. 
	 */
	@Override
	protected List<MinAreaPolygon> compute() {

		List<MinAreaPolygon> resultingPolygons;
		if(end - start <= THRESHOLD) {
			resultingPolygons = buildPolygon();
		} else {
			int middle = start + (end - start) / 2;
			BitmapTraverserTask taskLeft = new BitmapTraverserTask(bitMap, indexToXCoordinate,
					indexToYCoordinate, start, middle, errorLogger, minArea);
			taskLeft.fork();
			
			BitmapTraverserTask taskRight = new BitmapTraverserTask(bitMap, indexToXCoordinate,
					indexToYCoordinate, middle + 1, end, errorLogger, minArea);
			
			List<MinAreaPolygon> polygonsRight = taskRight.compute();
	        List<MinAreaPolygon> polygonsLeft = taskLeft.join();
	        
	        resultingPolygons = mergePolygons(polygonsLeft, polygonsRight);
	    }
	    
	    return resultingPolygons;
	}

	/*
	 * Merge all polygons on the left side of the vertical border with those on the right
	 * side if they are connected with each other by at least one adjoining point.
	 */
	private List<MinAreaPolygon> mergePolygons(List<MinAreaPolygon> polygonsLeft,
			List<MinAreaPolygon> polygonsRight) {
		
		List<MinAreaPolygon> results = new ArrayList<MinAreaPolygon>();
		List<List<MinAreaPolygon>> linkedSets = new ArrayList<List<MinAreaPolygon>>();
		 //Build up all correlation components by traversing
        while(!polygonsLeft.isEmpty()) {
          MinAreaPolygon root = polygonsLeft.get(0);
          polygonsLeft.remove(0);
    	  root.setSide(Side.Left);
    	  linkedSets.add(travers(root, polygonsLeft, polygonsRight));
        }
    	for(MinAreaPolygon polyRight : polygonsRight) {
    	    List<MinAreaPolygon> single = new ArrayList<MinAreaPolygon>();
    	    polyRight.setSide(Side.Right);
    	    single.add(polyRight);
    	    linkedSets.add(single);
    	 
    	}
    	
    	//Merge the resulting correlation components to one single area in each case
    	for(List<MinAreaPolygon> linkedSet : linkedSets) {
    		MinAreaPolygon result;
    		if(linkedSet.size() > 1) {
    			result = merge(linkedSet);
    		} else {
    			result = linkedSet.get(0);
    		}
    		//If the resulting polygon is enclosed, it can be checked whether it exceeds
    		//the minimum size. Otherwise report it.
    		if(isConnectedToNeighbor(result)) {
					
					if(result.getArea() < minArea) {
						errorLogger.reportMinAreaViolation(
								result.getArea(), 
								indexToXCoordinate[result.getUpperRight().getX() + 1], 
								indexToYCoordinate[result.getUpperRight().getY() + 1], 
								null);  
					} 
			//If there is still a connection to other stripes, continue merging.
    		} else {
    			results.add(result);
    		}
    	}
		return results;
	}
	
	/**
	   * Traverses through the lists leftAreas and rightAreas via the 
	   * Depth-First Search starting from the given area. During traversal 
	   * connected areas get collected in a list, so that all
	   * correlation components may be merged in a further step.
	   * 
	   * @return the list of all correlation components
	   */
	  private List<MinAreaPolygon> travers(MinAreaPolygon curr, 
			  List<MinAreaPolygon> leftAreas, 
			  List<MinAreaPolygon> rightAreas) {
		List<MinAreaPolygon> linked = new ArrayList<MinAreaPolygon>();
	    linked.add(curr);
	    Iterator<MinAreaPolygon> it = null;
	    if(curr.getSide().equals(Side.Right)) {
	      it = leftAreas.iterator();
	      while(it.hasNext()) {
	        MinAreaPolygon next = it.next();
	        next.setSide(Side.Left);
	        
	        if(next.overlap(curr)) {
	          it.remove();
	          linked.addAll(travers(next, leftAreas, rightAreas));
	          it = leftAreas.iterator();
	        }
	      }
	    } else {
	      it = rightAreas.iterator();
	      while(it.hasNext()) {
	        MinAreaPolygon next = it.next();
	        next.setSide(Side.Right);
	        
	        if(curr.overlap(next)) {
	          it.remove();
	          linked.addAll(travers(next, leftAreas, rightAreas));
	          it = rightAreas.iterator();
	        }
	      }
	    }
	    
	    return linked;
	  }
	  
	  /**
	   * Merges all specified polygons to one single polygon in the following way:
	   * 
	   * 1. add the sizes of each area
	   * 2. combine all ranges on the most left of each area marked as left side
	   * 3. combine all ranges on the most right of each area marked as right side
	   * 4. actualize the vertical borders of the resulting polygon
	   * 5. update the most upper right point
	   * 
	   */
	  private MinAreaPolygon merge(List<MinAreaPolygon> listOfPolygons) {
	    
		MinAreaPolygon result = new MinAreaPolygon();
		for(MinAreaPolygon poly : listOfPolygons) {
			result.addArea(poly.getArea());
			
	      if (poly.getSide().equals(Side.Left)) {
	    	  result.addRangesLeft(poly.getRangesLeft());
	    	  result.setMinPos(poly.getMinPos());
	      } else if (poly.getSide().equals(Side.Right)) {
	    	  result.addRangesRight(poly.getRangesRight());
	    	  result.setMaxPos(poly.getMaxPos());
	      }
	      result.setUpperRight(poly.getUpperRight());
	    }
	    return result;
	  }
	
	/**
	 * Builds up one particular polygon within the corresponding stripe.
	 * Therefore the algorithm searches for an initial range of set bit in 
	 * the bitmap and examines all contiguous ranges iteratively. 
	 * @return
	 */
	private List<MinAreaPolygon> buildPolygon() {
		
		List<MinAreaPolygon> resultingAreas = new ArrayList<MinAreaPolygon>();
		
		int x = start;
		
		while (x <= end) {
			
		   int y = 0;
		   
		   while(y < indexToYCoordinate.length) {
			   
			   //Look up for start of the range within this column
			   int startOfInnerRange = bitMap[x].nextSetBit(y);
			   if(startOfInnerRange < 0) {
				   break;
			   } 
			   y = startOfInnerRange;
			   //Look up for the end of the range within this column
			   int endOfInnerRange = bitMap[x].nextClearBit(y) - 1;
			   if(endOfInnerRange < 0) {
				   endOfInnerRange = indexToYCoordinate.length - 1;
			   }
			   y = endOfInnerRange + 1;
			   
			   Stack<Pair<Integer, Pair<Integer, Integer>>> stack 
		   		= new Stack<Pair<Integer, Pair<Integer, Integer>>>();
		   
			   //Initialize the polygon
			   MinAreaPolygon polygon = new MinAreaPolygon();
			   long polySize = 0;
			   
			   polygon.setUpperRight(new Point(x, endOfInnerRange));
			   polygon.addRangeLeft(x, startOfInnerRange, endOfInnerRange);
			   polygon.addRangeRight(x, startOfInnerRange, endOfInnerRange);
			   polySize += calculateDistance(x, startOfInnerRange, endOfInnerRange);
			   
			   stack.push(new Pair<Integer, Pair<Integer, Integer>>
			   			(x, new Pair<Integer, Integer>(startOfInnerRange, endOfInnerRange)));
			   
			   //Iteratively examine all neighbor ranges till no further range
			   //can be found.
			   while(!stack.isEmpty()) {
				   Pair<Integer, Pair<Integer, Integer>> currRange = stack.pop();
				   int sizeOfStack;
				   do {
					   sizeOfStack = stack.size();
					   int currIndex = currRange.getFirst() - 1;
					   if(currIndex >= start)
						   polySize = examineNeighbor(stack, polygon, polySize, currRange, currIndex);
					   currIndex = currRange.getFirst() + 1;
					   if(currIndex <= end)
						   polySize = examineNeighbor(stack, polygon, polySize, currRange, currIndex);
				   } while(stack.size() != sizeOfStack);
			   }

			   polygon.setArea(polySize);
			   
			   //If this polygon is enclosed within this stripe, the polygon 
			   //is completely build up and can be examined for its size. 
			   if(isConnectedToNeighbor(polygon)) {
						
					if(polygon.getArea() < minArea) {
							errorLogger.reportMinAreaViolation(
									polygon.getArea(), 
									indexToXCoordinate[polygon.getUpperRight().getX() + 1], 
									indexToYCoordinate[polygon.getUpperRight().getY() + 1], 
									null);  
					} 
				//Otherwise return it as a polygon that might has to be merged
				//with another nearby polygon.
				} else {
					resultingAreas.add(polygon);
				}
		   }
		   x++;
		}
		return resultingAreas;
	}

	/*
	 * Checks whether the specified polygon has either a connection to
	 * the left or right stripe of the bitmap. If no connection could be 
	 * found, the polygon is completely build up and can be examined for 
	 * its size. 
	 * 
	 * @param polygon
	 * @return
	 */
	private boolean isConnectedToNeighbor(MinAreaPolygon polygon) {
		return (start == 0 || !polygon.hasConnectionToLeft(start))
					&& (end == bitMap.length - 1 || !polygon.hasConnectionToRight(end));
	}

	/*
	 * Looks up in the bitmap if the current polygon has a contiguous range of set 
	 * bit in the specified column. The size of this neighbor is added to the result
	 * and the range of this neighbor is put on the stack to build up the whole
	 * polygon iteratively.
	 */
	private long examineNeighbor(
			Stack<Pair<Integer, Pair<Integer, Integer>>> stack,
			MinAreaPolygon polygon, long polySize,
			Pair<Integer, Pair<Integer, Integer>> currRange, int currIndex) {
		int startNextRange = bitMap[currIndex]
				   .nextSetBit(currRange.getSecond().getFirst());
		   if(startNextRange >= 0 && startNextRange <= currRange.getSecond().getSecond()) {
			   
			   do {
				   if(startNextRange > 0 && bitMap[currIndex].get(startNextRange - 1)) {
					   startNextRange--;
				   } else
					   break;
			   } while(true);
			   
			   int endNextRange = bitMap[currIndex]
					   .nextClearBit(startNextRange) - 1;
			   polySize += calculateDistance(currIndex, startNextRange, endNextRange);
			   polygon.addRangeLeft(currIndex, startNextRange, endNextRange);
			   polygon.addRangeRight(currIndex, startNextRange, endNextRange);
			   polygon.setUpperRight(new Point(currIndex, endNextRange));
			   stack.push(new Pair<Integer, Pair<Integer, Integer>>
			   		(currIndex, new Pair<Integer, Integer>(startNextRange, endNextRange)));
		   }
		return polySize;
	}

	/*
	 * Calculates the real distance of a rectangle within the bitmap
	 * specified by its x-index and its y-range.
	 */
	private long calculateDistance(int x, int start, int end) {
	      long w = indexToXCoordinate[x + 1] - indexToXCoordinate[x];
	      long h = indexToYCoordinate[end + 1] - indexToYCoordinate[start];
	      bitMap[x].clear(start, end + 1);
	      return w * h;
	} 
}
